package sol.leetcode;

import java.util.*;

/**
 * Ugly Number II
 */
public class Issue264 {
    public int nthUglyNumber(int n) {
        int[] found = new int[n];

        found[0] = 1;

        //存储每个素数对应的一个丑数下标
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(2, 0);
        map.put(3, 0);
        map.put(5, 0);

        for (int i = 1; i < n; ++i) {
            int next = Integer.MAX_VALUE;//下一个丑数
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                next = Math.min(entry.getKey() * found[entry.getValue()], next);
            }
            found[i] = next;

            //更新每个素数对应的下标
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                int prime = entry.getKey();
                int idx = entry.getValue();
                while (prime * found[idx] <= next)
                    idx++;
                entry.setValue(idx);
            }
        }

        return found[n - 1];
    }

    public static void main(String[] args) {
        Issue264 sol = new Issue264();
        int n = 10;
        System.out.println(sol.nthUglyNumber(n));
    }
}
